COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Most of this is Carolyn's idea and first version is in Seus
C00006 00003	 Here we use numbers as selectors to distinguish them from the ordinary
C00008 ENDMK
C⊗;
Most of this is Carolyn's idea and first version is in Seus

nodesc[x,n,u] ← qif x ε u qthen <n,u>
		qelse qif qat x qthen <n+1, x.u>
		qelse nodesc[qa x, nodesc[qd x, n+1, x.u]]

This gives the number of nodes and a list of the nodes in a possibly
cyclic list structure.  The function has 3 arguments and gives
2 outputs.  This is how the inner nodesc[qd x, n+1, x.u] can
serve as two of the arguments of the outer ⊗nodesc.   

These multiple output functions are valuable and correspond
naturally to the structure of a stack machine.  However, they
aren't on the face of it translatable into first order logic
sentences.

The translation can be done provided we go to single argument
functions whose arguments and results are tuplets.  Here is
a jmc version of ⊗nodesc. 

nodesc α ← qif 1 α ε 3 α qthen 2 α : 3 α
	qelse qif qat 1 α qthen (2 α) + 1 : 1 α . 3 α
	qelse nodesc qa 1 α : nodesc qd 1 α : (2 α) + 1 : 1 α . 3 α

Here we are using numbers as selectors on tuples and : as the
concatenator for tuples.  The tuples aren't lists, because a tuple
cannot be an element of a tuple.  It is like linear LISP.

Here is a debugged maclisp version of the program taken from cyclic.lsp[e80,jmc]

(defun nodesc (w) (if
	(member (car w) (caddr w)) 
	(list (cadr w) (caddr w))
	(atom (car w))
	 (cons (add1 (cadr w)) (list (cons (car w) (caddr w))))
	 (nodesc (append (list (car (car w))) (nodesc (foo w))))))

(defun foo (w) (list (cdr (car w)) (add1 (cadr w)) (cons (car w) (caddr w))))

Here is one possible lispification of Carolyn's version that cculd perhaps
be translated into the above by a program.

(defun nodesc (x n u) (cond
	((member x u) n u)
	((atom x) (add1 n) (cons x u))
	(t (nodesc (car x) (nodesc (cdr x) (add1 n) (cons x u))))))

Here we are using triplets in the conditional expression to indicate
that there are two outputs rather than the usual MACLISP hack of
including extra terms for their side effects.
There is certainly a large difference in clarity between the
last term of the lispification and the actual lisp progam.
;;; Here we use numbers as selectors to distinguish them from the ordinary
;;; cars and cdrs.

(defun nodesc (w)
       (if
	(member (1 w) (3 w)) 
	(list (2 w) (3 w))
	(atom (1 w))
	(append
	 (list (add1 (2 w)))
	 (list (cons (1 w) (3 w))))
	(nodesc (append
		 (list (car (1 w)))
		 (nodesc (list
			  (cdr (1 w))
			  (add1 (2 w))
			  (cons (1 w) (3 w))))))))

;;; Here we have re-introduced the variables x, n and u, and we have completed
;;; the process of using different symbols for appending, listing and selecting
;;; from tuples, i.e. multiple outputs.

(defun nodesc (w)
       ((lambda (x n u)
		(if
		 (member x u)
		 (l n u)
		 (atom x)
		 (app
		  (l (add1 n))
		  (l (cons x u)))
		 (nodesc (app
			  (l (car x))
			  (nodesc (l
				   (cdr x)
				   (add1 n)
				   (cons x u)))))))
	(1 w) (2 w) (3 w)))

;;; A cons counting version of subst using multiple values.

(defun substc (x y z n)
       (cond
	((atom z) n (cond ((= z y) x) (t z)))
	(t ((lambda (w1 n1)
		    ((lambda (w2 n2) n2 (cons w1 w2))
		     (substc x y (car z) n1)))
	    (substc x y (car z) (add1 n))))))